package newview;

/**
 * 最大水王数问题
 * 一个数组中某个数出现的次数，大于数组长度的一半， 则该数是水王数
 * @author TANGYE
 * @date 2021/7/25 10:15 上午
 **/
public class ZuiDSWS {

    public static void main(String[] args) {
        int[] waters = new int[] {3,2,3,3,1,4,3,1,3,3,7,3,6,6,3};
        System.out.println(getWaterNum(waters));
    }

    public static int getWaterNum(int[] nums) {
        System.out.println(nums.length);

        // 血量
        int blood = 0;
        int num = 0;

        for (int i = 0; i < nums.length; i++) {
            // 血量为0，代表当前无候选，已经被抵消掉了
            if (blood == 0) {
                num = nums[i];
                blood = 1;
            } else if (nums[i] == num){
                blood++;
            } else {
                blood--;
            }
        }

        // 说明没有候选留下
        if (blood == 0) {
            return -1;
        }

        int scale = 0;
        for (int i : nums) {
            if (i == num) {
                scale++;
            }
        }
        return scale > (nums.length >> 1) ? num : -1;
    }
}
